package leetcode.链表;

/**
 * 445. 两数相加 II
 *
 * 给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 * 输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出: 7 -> 8 -> 0 -> 7
 *
 *
 */
public class Test445两数相加II {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static ListNode addTwoNumbersFromReverseList(ListNode l1, ListNode l2) {
        ListNode dummy1 = l1;
        ListNode dummy2 = l2;
        ListNode ans = new ListNode(0);
        ListNode node = ans;
        int carry = 0;
        while (dummy1 != null || dummy2 != null) {
            // sum 用来保存进位
            carry /= 10;
            if (dummy1 != null) {
                carry += dummy1.val;
                dummy1 = dummy1.next;
            }
            if (dummy2 != null) {
                carry += dummy2.val;
                dummy2 = dummy2.next;
            }
            node.next = new ListNode(carry % 10);
            node = node.next;
        }

        if (carry / 10 == 1)
            node.next = new ListNode(1);
        return ans.next;
    }


    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 1. 先反转链表
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        // 2. 计算和
        l1 = addTwoNumbersFromReverseList(l1, l2);
        // 3. 再反转回去
        return reverseList(l1);
    }
}
